「Luogu P3183」[HAOI2016]食物链 解题报告

$\mathtt{Update\ 2019.11.08}$

题面

求有向图的路径数

解题思路

直接在有向图上 $DP$ 即可

要注意的是单独一个点不算一条链

存图后把入度为 $0$ 且出度不为 $0$（即非单独）的点入队，类似拓扑地跑一个 $DP$

每次对一个出点 $to$ 更新之的答案 f[to]+=f[cur]

即利用加法原理，到 $to$ 点的方案为向它连边点的方案和

当该出点 $to$ 入度为 $0$ 时，分情况视之

倘若该出点出度为0时，累加答案 ans+=f[to]

否则就入队用来更新其他点

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define N 100003
using namespace std;
struct node{
    int to,nxt;
}b[N<<1];
int n,t,T,head[N];
int f[N],d[N],ans;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(int x,int y) {
    b[++t].to=y,b[t].nxt=head[x],head[x]=t;
}
inline void solve() {
    rint i,cur,to;queue<int>p;
    for(i=1;i<=n;i++)//初始化入度为0的点（不包括单独的点）
        if(!d[i]&&head[i])//分别判断入度为0和是否是单独的点
            f[i]=1,    p.push(i);//初始化路径数，否则全都是0
    while(!p.empty()) {
        cur=p.front(),p.pop();
        for(i=head[cur];i;i=b[i].nxt) {
            to=b[i].to,d[to]--,f[to]+=f[cur];
            if(d[to]==0) {
                if(!head[to]) ans+=f[to];
                else p.push(to);//只有入度为0且出度不为0时才入队
            }
        }
    }
}
int main()
{
    rint x,y;n=read(),T=read();
    while(T--) x=read(),add(x,read()),d[y]++;//入度
    solve(),printf("%d",ans);
    return 0;
}